Integrated circuit design is an increasingly complex process and relies heavily on the use of computer-based tools. In general terms, the design of an integrated circuit involves the translation of user specifications into lower level representations, and the optimization of those lower level representations. The sequence of steps used to go from a high level specification to a chip layout is known as a design flow.
In one embodiment of a design flow, a designer writes an RTL (register transfer level) representation of a circuit, which then gets translated into a collection of interconnected gates during an RTL synthesis phase. Then, during a physical synthesis phase, the gates representing the circuit get placed and optimized, resulting in a collection of placed gates. In the final stage, detailed routing is performed and an integrated circuit layout is generated.
RTL synthesis generally involves the translation of a design at an architectural level into individual gates, specified by a netlist of connected library components. Physical synthesis generally involves the translation and optimization of the netlist into placed gates. The optimization that is performed in conjunction with the physical synthesis phase typically involves techniques such as re-sizing of components, Boolean restructuring and buffer insertion.
Any stage in a design flow may be iterative, and often the results of one phase are fed back to an earlier phase. For example, if physical synthesis and optimization is not able to achieve the target clock frequency, the designer may re-structure the RTL representation of the circuit and then perform the RTL synthesis phase again.
Often integrated circuit design projects are very schedule constrained. In order to get a device manufactured and meet a market opportunity, it needs to be synthesized and optimized as quickly as possible. In the case of physical synthesis of large integrated circuits, designers often strive for performing iterations of optimizations where the optimization phase is run overnight. This allows analysis and refinement during the next day. As integrated circuits have increased in complexity, it is becoming increasingly difficult to optimize the physical synthesis satisfactorily within this allotted time frame.
For example, while chip capacity has quadrupled as feature sizes have decreased from 180 nanometers to 90 nanometers, integrated circuit design tool capacity for overnight closure has not increased by the same amount, resulting in delayed schedules and higher design resource costs. In current generation implementation tools, physical synthesis is often the biggest limitation on the overall design flow. Existing physical synthesis approaches rely extensively on computationally expensive techniques, such as iterative improvement and brute-force trial-based optimization resulting in long turnaround times.
One of the reasons the physical synthesis phase of an integrated circuit design is such a large limitation in current design flows is due to the complexity and scope of what needs to be performed. During physical synthesis, a circuit is typically optimized by replacing circuit elements to decrease the worst case delay through the circuit. Traditional physical synthesis approaches perform optimization by working on the design one path at a time. A path is a sequence of nodes that a signal travels along between a start point and an end point, where a node is a pin of a device. Typically, the worst path (i.e., the path that fails to meet the timing requirements by the greatest amount, also called the critical path) is identified and then optimized by traversing the nodes along this worst path and optimizing such nodes. This process is repeated sequentially on each and every worst path.
Path enumeration of all paths between start points and end points can be very expensive. Prior art methods rely on path enumeration to fix each path from start point to end point. Even if heuristics are employed to reduce the number of paths enumerated, the solution is still exponential in nature. This approach, being exhaustive, can yield good results when the design is constrained properly. However, as the size of the circuit graph grows, the time it takes to complete such exhaustive optimization becomes infeasible as the number of critical paths can grow exponentially.
Additionally, prior art techniques can very easily get trapped with one bad end point especially if it has a bad constraint. A bad constraint may create timing requirements that are impossible to meet. In such a case, the process may not converge and may cause impractically long runtimes even for small designs.
Thus, there is a need to reduce the computational effort required to optimize circuit designs during physical synthesis. In particular, there is a need to efficiently perform a global analysis of a circuit design, avoiding path enumeration, and still be able to visit sufficient nodes in the circuit graph to optimize the objective function. Additionally, there is a need to optimize a circuit design without getting distracted by bad constraints.